# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        node_map = {}
        def helper(node: 'Node'):
            if node in node_map:
                return node_map[node]
            node_clone = Node(node.val, [])
            node_map[node] = node_clone
            for sub_node in node.neighbors:
                node_clone.neighbors.append(helper(sub_node))
            return node_clone
        return helper(node)
